import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution102 {

    public static void main(String args[]){
        Solution102 s = new Solution102();
    }

    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(0, root));

        int preLevel = -1;
        List<Integer> l = new ArrayList<>();
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            if(cur.level > preLevel && l.size() > 0){
                ret.add(l);
                l = new ArrayList<>();
                preLevel = cur.level;
            }
            l.add(cur.treeNode.val);
            if(cur.treeNode.left != null){
                queue.add(new Node(cur.level + 1, cur.treeNode.left));
            }
            if(cur.treeNode.right != null){
                queue.add(new Node(cur.level + 1, cur.treeNode.right));
            }
        }
        if(l.size() > 0){
            ret.add(l);
        }
        return ret;
    }

    class Node{
        int level;
        TreeNode treeNode;
        public Node(int l, TreeNode t){
            this.level = l;
            this.treeNode = t;
        }
    }
}
